package leetcode.helper.tree;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.helper.HelpDebug;

/**
 * @author Max
 * @date 2021年8月19日
 * @description
 * @see Node
 */
public class NodeArray {

	public static void main(String[] args) {
		Integer[] array = new Integer[] { 1, 2, 3, 4, 5, 6, 7 };
		Node root = array2tree(array);
		String[] result = perfecttTree2array(root);
		HelpDebug.printArray(result);
	}

	public static String[] perfecttTree2array(Node root) {
		if (root == null)
			return null;
		Queue<Node> result = new LinkedList<>();
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			result.add(node);
			if (node == null) {
				continue;
			}
			if (node.left != null || node.right != null) {
				queue.add(node.left);
				queue.add(node.right);
			}
		}
		int len = result.size();
		int ext = 0;
		int temp = len;
		while (temp > 0) {
			temp >>= 1;
			ext++;
		}
		String[] array = new String[len + ext];
		for (int i = 0; i < len + ext; i++) {
			Node node = result.poll();
			if (node == null) {
				array[i] = null;
			} else {
				array[i] = String.valueOf(node.val);
				if (node.next == null) {
					i++;
					array[i] = "#";
				}
			}
		}
		return array;
	}

	public static Node array2tree(Integer[] array) {
		if (array == null || array.length == 0)
			return null;
		Node root = new Node();
		root.val = array[0];
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		int point = 1;
		int size = array.length;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			if (point < size) {
				Integer pi = array[point++];
				if (pi == null) {
					node.left = null;
				} else {
					Node left = new Node();
					left.val = pi;
					node.left = left;
					queue.add(left);
				}

			}
			if (point < size) {
				Integer pi = array[point++];
				if (pi == null) {
					node.right = null;
				} else {
					Node right = new Node();
					right.val = pi;
					node.right = right;
					queue.add(right);
				}
			}
		}
		return root;
	}

}
